#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//依次规划每一辆车的路线
//先在dijkstra算法中不对流量进行限制（K条最短路线算法，默认初始时取最短路线=1（记为s））
//找到路线后把这条路线加入列表中
//进行refresh函数检查更新后的每条路的流量
//refresh更新时要检查的内容：依次计算每一个时间段内（0秒~1秒，1秒~2秒，···）每条路的车流量，并且与restrictions[N][N]进行比较，flow可能需要改为使用3阶数组或3阶vector存储
//refresh函数会返回发生冲突的车辆编号car_id构成的vector
//若没有发生拥堵，则vector长度为0
//若某一段路发生了拥堵，则找出这条路有哪些车（n辆）参与了拥堵
//把新加入的这辆车和所有参与拥堵的车重新进行路线规划，找到每辆车第二短的路线
//找到能够最大程度消减用时的组合（即这n+1）辆车中有n辆采取第s短路线，1辆取第s+1短路线
//之后循环refresh检查是否存在问题（对于每一辆车，有一个专门的s变量存储其选取的是第几短的车）
//直到refresh结果没有问题为止（返回的vector长度为0）
//下面开始加入下一辆车的路线，重复上面的循环
//最后打印出结果

//refresh();//用于刷新整个流量矩阵

int**roadlength;


class PATH{
public:
    vector<int> path;
    int length;
    PATH(vector<int> path):path(path), length(length){}
    bool operator==(const PATH &other) const{
        return (path==other.path&&length==other.length);
    }
};

//找出
vector<int> dijkstra(int N, int start, int end) {
    //存储从起点到各节点的最短距离，前驱节点，节点是否已被访问
    vector<int> distance(N);
    vector<int> previous(N);
    vector<int> visited(N);

    //初始化，如果距离为无穷大，则说明起点和该点不直接连通，该点没有前驱节点
    for (int i = 0; i < N; i++) {
        distance[i] =roadlength[start][i];
        visited[i] = false;
        if (i!=start&&distance[i]<INT_MAX)previous[i]=start;
        else previous[i]=-1;
    }
    visited[start]=true;
    distance[start]=0;

    for (int i=0;i<N-1;i++){
        int min_distance = INT_MAX;
        int stop=start;
        for (int j=0;j<N;j++){
            if (!visited[j] && distance[j]<min_distance){
                min_distance=distance[j];
                stop=j;
            }
        }
        visited[stop]=true;
        for (int k=0;k<N;k++){
            if (!visited[k]&&roadlength[stop][k]<INT_MAX&& distance[stop]+roadlength[stop][k]<distance[k]){
                distance[k]=distance[stop]+roadlength[stop][k];
                previous[k]=stop;
            }
        }
    }
    
    return previous;
}
PATH printPath(vector<int> previous){
    vector<int> path;
    int length=0;
    int node=previous[previous.size()-1];
    while (node != -1) {
        path.push_back(node);
        length+=roadlength[node][previous[node]];
        node = previous[node];
    }
    reverse(path.begin(), path.end());
    return PATH(path);
}
vector<int> Yen(int N, int start,int end,int K){
    vector<int> previous=dijkstra(N,start,end);//首先有最短的路径方案
    vector<vector<int>> previouses;
    vector<PATH> paths;
    previouses.push_back(previous);
    paths.push_back(printPath(previous));
    while (paths.size()<K){
        int size = paths.size();
        for (int i=0;i<size;i++){//依次遍历每一种previous情况删去其前面的节点，规划路线
            vector<int> thepath = paths[i].path;
            for (int j=0;j<thepath.size()-1;j++){
                int temp=roadlength[thepath[j]][thepath[j+1]];
                roadlength[thepath[j]][thepath[j+1]]=INT_MAX;
                roadlength[thepath[j+1]][thepath[j]]=INT_MAX;
                vector<int> newprev=dijkstra(N,thepath[j],end);
                roadlength[thepath[j]][thepath[j+1]]=temp;
                roadlength[thepath[j+1]][thepath[j]]=temp;
                if (newprev.size()==1)continue;
                
            }
            
        }
    }
}
